// 二叉树按层序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
public class Code06_LevelorderSerializeAndDeserialize {

    // 不提交这个类
    // TreeNode类用于表示二叉树的节点，包含一个整数值val，以及左子节点left和右子节点right
    // 构造函数用于初始化节点的值
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    // 提交这个类
    // 按层序列化
    public class Codec {
        // 定义一个足够大的常量MAXN，用于表示存储二叉树节点的数组queue的最大容量
        public static int MAXN = 10001;
        // 定义一个TreeNode类型的数组queue，用于在序列化和反序列化过程中按层存储二叉树的节点
        public static TreeNode[] queue = new TreeNode[MAXN];
        // l和r分别表示队列queue的头指针和尾指针，用于在序列化和反序列化过程中操作队列
        public static int l, r;

        // 序列化方法，将二叉树转换为字符串
        public String serialize(TreeNode root) {
            StringBuilder builder = new StringBuilder();
            // 如果根节点不为空
            if (root!= null) {
                // 先将根节点的值添加到字符串中，后面跟一个逗号
                builder.append(root.val + ",");
                // 初始化队列的头指针l和尾指针r为0
                l = 0;
                r = 0;
                // 将根节点放入队列
                queue[r++] = root;
                // 按层遍历二叉树
                while (l < r) {
                    // 取出队列头部的节点
                    root = queue[l++];
                    // 如果当前节点的左子节点不为空
                    if (root.left!= null) {
                        // 将左子节点的值添加到字符串中，后面跟一个逗号
                        builder.append(root.left.val + ",");
                        // 将左子节点放入队列
                        queue[r++] = root.left;
                    } else {
                        // 如果左子节点为空，添加一个特殊标记'#'和逗号
                        builder.append("#,");
                    }
                    // 如果当前节点的右子节点不为空
                    if (root.right!= null) {
                        // 将右子节点的值添加到字符串中，后面跟一个逗号
                        builder.append(root.right.val + ",");
                        // 将右子节点放入队列
                        queue[r++] = root.right;
                    } else {
                        // 如果右子节点为空，添加一个特殊标记'#'和逗号
                        builder.append("#,");
                    }
                }
            }
            // 返回序列化后的字符串
            return builder.toString();
        }

        // 反序列化方法，将字符串转换为二叉树
        public TreeNode deserialize(String data) {
            // 如果传入的字符串为空，表示空树，直接返回null
            if (data.equals("")) {
                return null;
            }
            // 将字符串按照逗号分割成字符串数组，每个元素代表二叉树的一个节点值或特殊标记'#'
            String[] nodes = data.split(",");
            int index = 0;
            // 先创建根节点
            TreeNode root = generate(nodes[index++]);
            // 初始化队列的头指针l和尾指针r为0
            l = 0;
            r = 0;
            // 将根节点放入队列
            queue[r++] = root;
            // 按层构建二叉树
            while (l < r) {
                // 取出队列头部的节点
                TreeNode cur = queue[l++];
                // 构建当前节点的左子节点
                cur.left = generate(nodes[index++]);
                // 构建当前节点的右子节点
                cur.right = generate(nodes[index++]);
                // 如果左子节点不为空
                if (cur.left!= null) {
                    // 将左子节点放入队列
                    queue[r++] = cur.left;
                }
                // 如果右子节点不为空
                if (cur.right!= null) {
                    // 将右子节点放入队列
                    queue[r++] = cur.right;
                }
            }
            // 返回构建好的二叉树的根节点
            return root;
        }

        // 根据传入的字符串值创建节点，如果是'#'则返回null，否则创建一个新节点并返回
        private TreeNode generate(String val) {
            return val.equals("#")? null : new TreeNode(Integer.valueOf(val));
        }
    }
}